package org.example.leetcode;

import java.util.HashSet;

/**
 * @version 1.0.0
 * @author: lynn
 * @description:
 * @date: 2021/8/10 11:41
 */
public class LC52 {

    Boolean[][] board;
    HashSet<Integer> col,pie,na;
    int n;
    int res=0;
    public int totalNQueens(int n) {
        this.n=n;
        col=new HashSet<>();
        pie=new HashSet<>();
        na=new HashSet<>();
        board=new Boolean[n][n];
        dfs(0);
        return res;
    }
    private void dfs(int i){
        if (i==n){
            res++;
            return;
        }
        for (int j = 0; j <n ; j++) {
            if (col.contains(j)||pie.contains(i-j)||na.contains(i+j)) continue;
            board[i][j]=true;
            col.add(j);
            pie.add(i-j);
            na.add(i+j);
            dfs(i+1);
            board[i][j]=false;
            col.remove(j);
            pie.remove(i-j);
            na.remove(i+j);
        }
    }


    public static void main(String[] args) {
        LC52 lc=new LC52();
        System.out.println(lc.totalNQueens(2));
    }
}
